#include <stdlib.h>

#ifndef HASH_TABLE
#define HASH_TABLE

// #ifndef HashKeyType
// #define HashKeyType int
// #endif

// #ifndef HashValueType
// #define HashValueType int
// #endif

typedef struct HashNode {
    void* key;
    void* value;
    struct HashNode *next;
} HashNode;

typedef struct HashTable {
    int size;
    int capacity;
    HashNode *heads;
    // 计算 key 的哈希值
    int (*hash)(void*);
    // 比较两个 key 是否相等
    int (*sameKey)(void*, void*);
    // 销毁key, value
    void (*destroyKeyAndValue)(void*, void*);
} HashTable;

HashNode *createHashNode(void* key, void* value) {
    HashNode *node = (HashNode *) malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

// 计算不大于 capacity 的最大素数
int calcMaxPrime(int capacity) {
    int prime = capacity;
    while (1) {
        int flag = 1;
        for (int i = 2; i * i <= prime; i++) {
            if (prime % i == 0) {
                flag = 0;
                break;
            }
        }
        if (flag) break;
        prime--;
    }
    return prime;
}

// 计算不小于 N 的最小素数
int nextPrime(int n) {
    if(n <= 2)
		return 2;
	if (n == 3)
		return n;
    int prime = n % 2 == 0 ? n + 1 : n;
    while (1) {
        int flag = 1;
        for (int i = 2; i * i <= prime; i++) {
            if (prime % i == 0) {
                flag = 0;
                break;
            }
        }
        if (flag) break;
        prime += 2;
    }
    return prime;
}

HashTable *createHashTable(int capacity, int (*hash)(void*), int (*sameKey)(void*, void*), void (*destroyKeyAndValue)(void*, void*)) {
    HashTable *h = (HashTable *) malloc(sizeof(HashTable));
    h->size = 0;
    h->capacity = nextPrime(capacity);
    h->hash = hash;
    h->sameKey = sameKey;
    h->destroyKeyAndValue = destroyKeyAndValue;
    h->heads = (HashNode *) calloc(h->capacity, sizeof(HashNode));
    // for (int i = 0; i < capacity; i++) {
    //     h->heads[i].next = NULL;
    // }
    return h;
}

void destroyHashTable(HashTable *h) {
    for (int i = 0; i < h->capacity; i++) {
        for (HashNode *node = h->heads[i].next; node != NULL;) {
            HashNode *next = node->next;
            if (h->destroyKeyAndValue != NULL) {
                h->destroyKeyAndValue(node->key, node->value);
            }
            free(node);
            node = next;
        }
    }
    free(h->heads);
    free(h);
    return ;
}

int hashKey(int key, int capacity) {
    return key % capacity;
}

int insert(HashTable *h, void* key, void* value) {
    int index = hashKey(h->hash(key), h->capacity);
    for (HashNode *node = h->heads[index].next; node != NULL; node = node->next) {
        if (h->sameKey(node->key, key)) {
            node->value = value;
            return 0;
        }
    }
    h->size++;
    HashNode *node = createHashNode(key, value);
    node->next = h->heads[index].next;
    h->heads[index].next = node;
    return 1;
}

void* find(HashTable *h, void* key) {
    int index = hashKey(h->hash(key), h->capacity);
    for (HashNode *node = h->heads[index].next; node != NULL; node = node->next) {
        if (h->sameKey(node->key, key)) {
            return node->value;
        }
    }
    return NULL;
}

// 返回所有值的数组，需要手动 free
void** valueArray(HashTable *h, int *len) {
    void** ret = (void**) malloc(sizeof(void*) * h->size);
    int cnt = 0;
    for (int i = 0; i < h->capacity; i++) {
        for (HashNode *node = h->heads[i].next; node != NULL; node = node->next) {
            ret[cnt++] = node->value;
        }
    }
    *len = cnt;
    return ret;
}

#endif
